package com.zpself.module.算法练习.计算;

import java.util.HashMap;
import java.util.Map;

/**
 * @author By ZengPeng
 * @Description 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c
 * @date in  2021/1/20 19:13
 * @Modified By
 */
public class 力扣_633_平方数之和 {
    public static void main(String[] args) {

        System.out.println(myAnswer_up2(5));
    }

    /**
     *  两端法
     *
     **/
    private static  boolean  myAnswer_up2(int c){
        int  a= 0;
        int  b= (int)Math.sqrt(c);

        int  aa= 0;
        int  bb= b*b;

        while(a<=b){
            int result = aa+bb-c;
            if(result==0){
                return  true;
            }else if(result>0){
                bb = bb-(b<<1) +1;
                b--;
            }else{
                aa = aa+(a<<1) +1;
                a++;
            }
        }
        return false;
    }

    /**
     *  性能稍有提升
     *  从0- log a  的所有平方值，与a求差。用差值开方，判断是否为整数
     **/
    private static  boolean  myAnswer_up1(int c){
        int end = (int) Math.sqrt(c);
        for (int i = 0; i <= end; i++) {
            double a = Math.sqrt(c - i * i);
            if((int)a ==a)
                return  true;
        }
        return false;
    }


    /**
     *  性能稍差
     *  map存下从0- log a  的所有平方值， 用a相减是否存在集合中
    **/
    private static  boolean  myAnswer(int a){
        int end = (int) Math.sqrt(a);
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i <= end; i++) {
            map.put(i*i,i);
            if(map.containsKey(a-i*i))
                return  true;
        }
        return false;
    }
}
